// package list 链表相关题目
package list

import "fmt"

// https://leetcode-cn.com/problems/design-linked-list/
// 设计链表
// 设计思路: 通过指针实现链表
// 时间复杂度: O(n)
type MyLinkedList struct {
	head *Node
	tail *Node
	len int
}

// 单向链表
type Node struct {
	Val int
	Next *Node
}


func GetMyLinkedList() MyLinkedList {
	list := MyLinkedList{}
	return list
}

// 获取链表中第 index 个节点的值。如果索引无效，则返回-1
func (this *MyLinkedList) Get(index int) int {
	if (0 == this.len || index >= this.len) {
		return -1
	}
	currentNode := this.head
	for index > 0 {
		index--
		currentNode = currentNode.Next
	}
	return currentNode.Val
}

// 在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点
func (this *MyLinkedList) AddAtHead(val int)  {
	newNode := Node{Val: val}
	if this.head != nil {
		newNode.Next = this.head
	} else {
		this.tail = &newNode
	}
	this.head = &newNode
	
	this.len++
}

// 将值为 val 的节点追加到链表的最后一个元素
func (this *MyLinkedList) AddAtTail(val int)  {
	newNode := Node{Val: val}
	if this.tail != nil {
		this.tail.Next = &newNode
	} else {
		this.head = &newNode
	}
	this.tail = &newNode
	this.len++
}

// 在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。
// 如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点
// 这个方法很容易忘记修改 tail，一定要小心
func (this *MyLinkedList) AddAtIndex(index int, val int)  {
	if index <= 0 {
		this.AddAtHead(val)
	} else if index <= this.len {
		toInsertPreNode := this.head
		index--
		for index > 0 {
			toInsertPreNode = toInsertPreNode.Next
			index--
		}
		newNode := Node{Val: val}
		nextNode := toInsertPreNode.Next
		toInsertPreNode.Next = &newNode
		newNode.Next = nextNode
		if this.tail == toInsertPreNode {
			this.tail = &newNode
		}
		this.len++
	}
}

// 如果索引 index 有效，则删除链表中的第 index 个节点
// 这个方法很容易忘记修改 head 或者 tail
func (this *MyLinkedList) DeleteAtIndex(index int)  {
	if index < 0 || index >= this.len {
		return
	}
	if 0 == index {
		this.head = this.head.Next
		if this.head == nil {
			this.tail = nil
		}
	} else {
		toDeletePreNode := this.head
		index--
		for index > 0 {
			index--
			toDeletePreNode = toDeletePreNode.Next
		}
		if toDeletePreNode.Next == this.tail {
			this.tail = toDeletePreNode
		}
		if nil != toDeletePreNode.Next {
			toDeletePreNode.Next = toDeletePreNode.Next.Next
		} else {
			toDeletePreNode.Next = nil
		}
	}
	this.len--
}

// 以下是其他辅助方法
func (this *MyLinkedList) Len() int {
	return this.len
}

func (this *MyLinkedList) String() (ret string) {
	currentNode := this.head
	for nil != currentNode {
		if currentNode != this.head {
			ret += " -> "
		}
		ret += fmt.Sprintf("%d", currentNode.Val)
		currentNode = currentNode.Next
	}
	return
}

// 以下是和这道题无关的，其他数据类型的定义
type DoublyNode struct {
	Key int
	Val int
	Pre *DoublyNode
	Next *DoublyNode
}